#include <set>
#include <vector>
#include <iostream>
using std::cout;
using std::endl;
using std::set;
using std::vector;
using std::pair;

void test0()
{
    //set的特点：
    //1. set之中不能存放关键字相同的元素
    //2. set中的元素默认情况下按升序方式进行排列
    //
    //set的底层实现是红黑树 ==> 近似的AVL（平衡二叉树）
    //红黑树的特点:
    //1. 节点不是红色就是黑色
    //2. 根节点是黑色
    //3. 叶子节点是黑色
    //4. 不能有两个连续的节点是红色
    //5. 从根节点到每个叶子节点上的黑色节点数目相同
    // 
    //结论: 访问红黑树上某一个节点的时间复杂度为 O(logN)
    //近似于二分查找的时间复杂度
    //
    //set<int> numbers;
    vector<int> arr{9, 6, 2, 3, 4, 7, 8, 1, 2, 3, 4, 5};
    set<int> numbers(arr.begin(), arr.end());
    cout << "numbers'size():" << numbers.size() << endl;
    for(auto it = numbers.begin(); it != numbers.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    //通过迭代器获取某一个节点之后，不能修改节点的元素
    auto it = numbers.begin();
    //*it = 10;//error
    
    //尽可能使用的是其查找功能
    //count
    int cnt = numbers.count(10);
    cout << "cnt:" << cnt << endl;

    //find
    set<int>::iterator pos = numbers.find(10);
    if(pos == numbers.end()) {
        cout << "查找失败" << endl;
    } else {
        cout << "查找成功" << endl;
        cout << "*pos:" << *pos << endl;
    }
}

void test1()
{
    set<int> numbers{9, 9, 6, 2, 3, 4, 7, 8, 1, 2, 3, 4, 5};
    for(auto & num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    //使用insert进行元素的添加
    //迭代器可以看成是指针
    pair<set<int>::iterator, bool>  ret = numbers.insert(5);
    if(ret.second) {
        cout << "添加成功" << endl;
    } else {
        cout << "添加失败" << endl;
    }
    cout << *ret.first << endl;
    cout << *ret.first << endl;

    //set不支持下标访问运算符
    //cout << numbers[0] << endl;
    
    auto it = numbers.begin();
    ++it;//支持向前遍历
    --it;//支持向后遍历
    //it = it + 1;//不支持随机访问
    
    numbers.clear();
}

void test2()
{
    std::pair<int, int> numpairs;
    numpairs.first = 1;
    numpairs.second = 1;
    cout << numpairs.first << " --> " << numpairs.second << endl;

    //pair类型之中有两个对象成员,分别是first和second
    std::pair<std::string, std::string> city;
    city.first = "027";
    city.second = "武汉";
    cout << city.first << " --> " << city.second << endl;
}


int main()
{
    /* test0(); */
    test1();
    /* test2(); */
    return 0;
}

